import jdk.internal.org.objectweb.asm.Handle;

public class MyLinkedList {

    static class ListNode{
      private int val;
      private ListNode prev;
      private  ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//头
    public ListNode last;//尾巴
    //头插法
public void addFirst(int data){
    ListNode node=new ListNode(data);
    if (head==null){
        head=node;
        last=node;
    }else{
        node.next=head;
        head.prev=node;
        head=node;
    }
}
  //尾插法
  public void addLast(int data)  {
ListNode node=new ListNode(data);
ListNode cur=head;
if (head==null){
    head=node;
    last=node;
}else{

   last.next=node;
   node.prev=last;
   last=node;
}
  }
  //删除第一次出现关键字为key的节点
    public void remove(int key){
ListNode cur=head;
while (cur!=null){
    if (cur.val==key){
     //是头节点
        if (head.val==key){
            if (head.next==null){
                head=null;
            }else {
                head=head.next;
                head.prev=null;
            }
        }else {//尾巴节点和中间节点
            if (cur.next==null){
                last=last.prev;
                last.next=null;
            }else {
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }

        }


        return;
    }else {
        cur=cur.next;
    }
}

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==key){
                //是头节点
                if (head.val==key){
                    if (head.next==null){
                        head=null;
                    }else {
                        head=head.next;
                        head.prev=null;
                    }
                }else {//尾巴节点和中间节点
                    if (cur.next==null){
                        last=last.prev;
                        last.next=null;
                    }else {
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }

                }

                cur=cur.next;
            }else {
                cur=cur.next;
            }
        }

    }

  //得到链表长度
  public int size(){
      int count=0;
      ListNode cur=head;
      while (cur!=null){
          count++;
          cur=cur.next;
      }
      return count;
  }
    //任意位置插入
   public void addIndex(int index,int data){

    if (index<0||index>size()){
        System.out.println("index位置不合法");
    }
    if (index==0){
        addFirst(data);
        return;
    }
    if (index==size()){
        addLast(data);
     return;
    }
       ListNode node=new ListNode(data);
       ListNode cur=head;
       int count=index;
       while (count>0){
           cur=cur.next;
           count--;
       }
      node.next=cur;
       cur.prev.next=node;
       node.prev=cur.prev;
       cur.prev=node;
   }
   //查找关键字key是否在链表中

   public boolean contains(int key){
       ListNode cur=head;
       while (cur!=null){
        if (cur.val==key){
            return true;
        }
           cur=cur.next;
       }
       return false;
   }



    //打印链表
    public void display(){
    ListNode cur=head;
    while (cur!=null){
        System.out.print(cur.val+" ");
        cur=cur.next;
    }

    }
    //清空链表
    public void clear(){

    ListNode cur=head;
    while (cur!=null){
        ListNode nextNode=cur.next;
        cur.prev=null;
        cur.next=null;
        cur=nextNode;
    }
    head=null;
    last=null;
    }


}
